package me.zk.practice1.s;

import java.util.Arrays;

/**
 * 215
 * @Author: zhang kai
 * @Date: 2023/05/09
 * @Description:
 */
public class S16 {

    public static void main(String[] args) {
        System.out.println(findKthLargest(new int[]{3,2,1,5,6,4},2));
    }

    public static int findKthLargest(int[] nums, int k) {
        int l = 0, r=nums.length-1,target = nums.length-k;
        while (l<r){
            int mid = quickSort(nums,l, r);
            if (mid == target) {
                return nums[mid];
            } else if(mid < target) {
                l = mid+1;
            } else {
                r = mid - 1;
            }
        }
        return nums[l];
    }

    public static int quickSort(int[] nums, int l, int r) {

        int i = l + 1, j = r;
        while (true) {
            while (i < r && nums[i] <= nums[l]) {
                ++i;
            }
            while (l < j && nums[j] >= nums[l]) {
                --j;
            }
            if (i >= j) {
                break;
            }
            swap(nums,i,j);
        }
        swap(nums,l,j );
        return j;
    }


    public static void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

}
